package com.dmall.graph.floodfill;

/**
 * @author: xiao1.wang
 * @date: 2022/6/19 22:46
 */
public class Solution200 {

    private boolean[][] visited;
    private int count = 0;
    private int R, C;

    private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public int numIslands(char[][] grid) {
        R = grid.length;
        C = grid[0].length;
        this.visited = new boolean[R][C];

        for (int x = 0; x < R; x++) {
            for (int y = 0; y < C; y++) {
                if (!visited[x][y] && grid[x][y] == '1') {
                    dfs(grid, x, y);
                    count ++;
                }
            }
        }

        return count;
    }

    private void dfs(char[][] grid, int x, int y) {
        visited[x][y] = true;
        for (int d = 0; d < 4; d++) {
            int nextx = x + dirs[d][0];
            int nexty = y + dirs[d][1];
            if (inArea(nextx, nexty) && !visited[nextx][nexty] && grid[nextx][nexty] == '1') {
                dfs(grid, nextx, nexty);
            }
        }
    }

    private boolean inArea(int r, int c) {
        return r >= 0 && r < R && c >= 0 && c < C;
    }

    public static void main(String[] args) {
        char[][] grid = {
                {'0', '0', '1', '0', '0', '0', '0', '1', '0', '0', '0', '0', '0'},
                {'0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '0', '0', '0'},
                {'0', '1', '1', '0', '1', '0', '0', '0', '0', '0', '0', '0', '0'},
                {'0', '1', '0', '0', '1', '1', '0', '0', '1', '0', '1', '0', '0'},
                {'0', '1', '0', '0', '1', '1', '0', '0', '1', '1', '1', '0', '0'},
                {'0', '0', '0', '0', '0', '0', '0', '0', '0', '0', '1', '0', '0'},
                {'0', '0', '0', '0', '0', '0', '0', '1', '1', '1', '0', '0', '0'},
                {'0', '0', '0', '0', '0', '0', '0', '1', '1', '0', '0', '0', '0'}
        };
        Solution200 solution200 = new Solution200();
        System.out.println(solution200.numIslands(grid));
    }
}
